public class Main{
    public static void main(String[] args) {

    }
    public static void mergeSort(int[] array) {
        divid(array, 0, array.length - 1);
    }

    private static void divid(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) >>> 1;
        divid(array, left, mid);
        divid(array, mid + 1, right);
        merge(array, left, right, mid);
    }

    private static void merge(int[] array, int left, int right, int mid) {
        // 其实就是合并两个数组，并使合并后的数组有序
        int l1 = left;
        int l2 = mid + 1;
        int[] tmp = new int[right - left + 1];
        int i = 0;
        while (l1 <= mid && l2 <= right) {
            // 为什么要加等号，防止死循环
            if (array[l1] <= array[l2]) {
                tmp[i++] = array[l1++];
            }
            if (array[l2] <= array[l1]) {
                tmp[i++] = array[l2++];
            }
        }
        // 判断哪个数组还有数据
        while (l1 <= mid) {
            tmp[i++] = array[l1++];

        }
        while (l2 <= right) {
            tmp[i++] = array[l2++];
        }
        for (int j = 0; j < tmp.length; j++) {
            array[j + left] = tmp[j];
        }
    }
}